package com.ycz.algorithm.utils.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author yancz
 * @ClassName BinarySearchTree
 * @description: 二叉搜索树，满足左子树中节点值 < 根节点值 < 右子树中节点值
 * @date 2024-12-19 15:36:20
 * @version: 1.0
 */
public class BinarySearchTree {

    // 静态内部类
    private static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int num) {
            val = num;
            left = null;
            right = null;
        }
    }

    private TreeNode root;

    // 查找节点
    public TreeNode searchNode(int num) {
        TreeNode currentNode = root; // 令当前节点指向根节点，从根节点开始查找
        while (currentNode != null) {
            if (currentNode.val < num) { // 大于当前节点值，在右子树中
                currentNode = currentNode.right;
            } else if (currentNode.val > num) { // 小于当前节点值，在左子树中
                currentNode = currentNode.left;
            } else {
                return currentNode; // 等于当前节点值，找到元素，直接返回
            }
        }
        return null;
    }

    // 插入节点
    public void insertNode(int num) {
        if (root == null) {
            root = new TreeNode(num);
            return;
        }
        TreeNode current = root, pre = null;
        while (current != null) {
            if (current.val == num) {
                return;
            }
            pre = current;
            if (current.val < num) { // 在右子树
                current = current.right;
            } else { // 在左子树
                current = current.left;
            }
        }
        TreeNode node = new TreeNode(num);
        if (pre.val < num) {
            pre.right = node;
        } else {
            pre.left = node;
        }
    }

    // 删除节点
    public void remove(int num) {
        if (root == null) return;
        TreeNode current = root, pre = null;
        while (current != null) {
            if (current.val == num) break;
            pre = current;
            if (current.val < num) {
                current = current.right;
            } else {
                current = current.left;
            }
        }
        if (current == null) return;
        if (current.left == null || current.right == null) { // 左子树或右子树为空时
            TreeNode child = current.left != null ? current.left : current.right;
            if (current != root) {
                if (pre.left == current) {
                    pre.left = child;
                } else {
                    pre.right = child;
                }
            }
            if (current == root) {
                root = child;
            }
        }
        if (current.left != null && current.right != null) { // 左右子树都不为空时
            TreeNode temp = current.right;
            while (temp.left != null) {
                temp = temp.left;
            }
            // 递归删除节点
            remove(temp.val);
            current.val = temp.val;
        }
    }

    // 层序遍历
    public void levelOrder() {
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        System.out.println("层序遍历：");
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val + "\t");
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        System.out.println();
    }

    // 前序遍历
    public void preOrder(TreeNode root) {
        if (root == null) return;
        System.out.print(root.val + "\t");
        preOrder(root.left);
        preOrder(root.right);
    }

    // 中序遍历
    public void midOrder(TreeNode root) {
        if (root == null) return;
        midOrder(root.left);
        System.out.print(root.val + "\t");
        midOrder(root.right);
    }

    // 后序遍历
    public void postOrder(TreeNode root) {
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + "\t");
    }

    public static void main(String[] args) {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insertNode(8); // 根节点
        binarySearchTree.insertNode(4);
        binarySearchTree.insertNode(2);
        binarySearchTree.insertNode(6);
        binarySearchTree.insertNode(12);
        binarySearchTree.insertNode(10);
        binarySearchTree.insertNode(14);
        binarySearchTree.printCommon(binarySearchTree);
        // 添加新的节点
        binarySearchTree.insertNode(1);
        binarySearchTree.insertNode(13);
        binarySearchTree.printCommon(binarySearchTree);
        // 删除节点
        binarySearchTree.remove(13);
        binarySearchTree.remove(1);
        binarySearchTree.printCommon(binarySearchTree);
    }

    public void printCommon(BinarySearchTree binarySearchTree) {
        binarySearchTree.levelOrder();
        TreeNode root = binarySearchTree.root;
        System.out.println("前序遍历：");
        binarySearchTree.preOrder(root);
        System.out.println();
        System.out.println("中序遍历：");
        binarySearchTree.midOrder(root);
        System.out.println();
        System.out.println("后序遍历：");
        binarySearchTree.postOrder(root);
        System.out.println();
        System.out.println("-------------------------------");
    }

}
